package com.zsj.doin;

import org.junit.jupiter.api.Test;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
import java.text.SimpleDateFormat;
import java.util.*;

/**
 * @auther zsj
 * @Date 2022/2/1
 **/
public class alg {

    /**
     * 卡片 问题
     * 0-9的卡片有2021张卡片
     * 每次拼一个数字
     * 会耗费卡片
     * 问最大能拼多大
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] cards = new int[10];
        for (int i = 0; i < 10; i++) {
            cards[i] = 2021;
        }
        int i;
        a:
        for (i = 1; ; i++) {
            int temp = i;
            while (temp != 0) {
                //一开始肯定不为0的,我们分解这个数字，然后减去指定卡片的数量
                int t = temp % 10;
                if (cards[t] <= 0) {
                    break a;
                }
                cards[t]--;
                temp /= 10;
            }
        }
        System.out.println(i - 1);


        //dfs

//        int count = 0;
//        for (int i = 1; i <= 2020; i++) {
//            int temp = i;
//            while (temp!=0){
//                int n = temp%10;
//                if (n == 2){
//                    count++;
//                }
//                temp/=10;
//            }
//        }
//        System.out.println(count);
    }


    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     * <p>
     * 如果数组中不存在目标值 target，返回int[-1, -1]。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] arr = new int[]{-1, -1};
        if (nums.length == 0) {
            return arr;
        }
        if (nums.length == 1) {
            if (nums[0] == target) {
                arr[0] = 0;
                arr[1] = 0;
                return arr;
            }
        }
        int index = 0;
        int end = nums.length - 1;
        for (int i = 0; i <= nums.length - 1; i++) {
            if (nums[i] == target) {
                int temp = i;
                if (index > 0) {
                    index = 1;
                }
                arr[index] = temp;
                index += 1;
            }
        }

        if (arr[1] == -1) {
            arr[1] = arr[0];
        }
        return arr;
    }


    /**
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ...,
     * nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     * <p>
     * <p>
     * todo
     */
    public static int search(int[] nums, int target) {

        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        //将倒转的数组进行分割，分割出来的数组一定有一组是有序的，在有序的里面寻找，没找到在无序里在分，在找，直至找到
        int begin = 0;
        int end = nums.length - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            //开始二分
            if (nums[mid] == target) {
                return mid;
            }
            //分区间，数组分区之后
            //123456 ----  456123 target = 5  like that
            //将数据按照二分法之后，从6开始分，45   6123 一定有一组是有序的,我们在不同的数组中寻找目标值即可
            if (nums[0] < nums[mid]) {
                //说明左边是有序列表
                if (nums[0] <= target && target < nums[mid]) {
                    //target在列表左边
                    end = mid - 1;
                } else {
                    begin = mid + 1;
                }
            } else {
                if (target < nums[end] && nums[mid] <= target) {
                    //target在列表右边
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }

            }

        }
        return -1;
    }

    //111111

    /**
     * 编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
     * <p>
     * 每行中的整数从左到右按升序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     * 输出：true
     * 思路  因为是二维数组，
     */
    public static boolean searchMatrix(int[][] matrix, int target) {


        //开始下标
        int begin = 0;
        //结束下标
        //每一行的数量
        int m = matrix[0].length - 1;
        //总行数
        int n = matrix.length - 1;

        if (n == 0) {
            return false;
        }
        while (begin <= m) {
            int mid = (begin + m) / 2;
            //现在开始判断比较target在哪个区间中，然后依次二分寻找，找到了就将flag改为true
            while (matrix[begin][m] < target) {
                //当前下标值最大小于目标值就将begin + 1 ,往下一行去寻找
                begin += 1;
            }
            //寻找结果值
            if (matrix[begin][mid] == target) {
                return true;
            }
            //开始在第二区间依次寻找值，因为上面判断过，target是在当前区间的，我们就将当前区间二分寻找即可
            while (mid <= m && mid > 0) {

                //找到了
                if (matrix[begin][mid] == target) {
                    return true;
                }

                //todo
                //现在的情况是，压根没有这个值，在当前区间中没有寻找到这个值之后，应该直接判断没有
                if (matrix[begin][mid] < target) {
                    //当前值小于目标值,往后找
                    mid += 1;
                    if (mid != m) {
                        if (matrix[begin][mid + 1] != target) {
                            return false;
                        }
                    }
                } else if (matrix[begin][mid] > target) {
                    //当前值大于目标值，往前找
                    mid -= 1;
                    if (mid != 0 && mid != m) {
                        if (matrix[begin][mid - 1] != target) {
                            return false;
                        }
                    }
                }

            }
        }

        return false;

    }


    //222222
    public boolean searchMatrix2(int[][] matrix, int target) {

        return false;
    }

    /**
     * 小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组 成，
     * 有些单词很长  远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，
     * 而是根据单词中哪个字母出现得最多来分辨单词。
     * 现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这 个字母出现的次数。
     * <p>
     * 97 -122  a -z
     * <p>
     * 这种题，用一个二十六位数组进行存储，用当前的char减去-‘a’ 再+1就等于它的数组下标值
     * 就可以拿到数量，然后再检索这个数组中的最大值，最大的那一个就是我们的最多的字母
     * <p>
     * aci值 -‘a’ ==数组下标
     */
    public static void findSmallAndCount(String list) {

        int[] b = new int[26];
        char name = 'a';//最终输出结果
        byte[] bytes = list.getBytes(StandardCharsets.UTF_8);//字母数组
        for (int i = 0; i < bytes.length; i++) {
            int address = (bytes[i] - 'a');
            b[address] += 1;
        }

        int temp = b[0];
        for (int i = 1; i < b.length; i++) {
            if (b[i] > temp) {
                temp = b[i];
                name = (char) (i + 'a');
            }
        }

        System.out.println(name);
        System.out.println(temp);

    }

    /**
     * 小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
     * <p>
     * 如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。
     * <p>
     * 请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数
     */
    public static void Demo() {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int students = scan.nextInt();
        int arr[] = new int[students];
        for (int i = 0; i < students; i++) {
            arr[i] = scan.nextInt();
        }
        //拿到了所有学生的成绩
        int jige = 0;
        int good = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 60) {
                //学生及格
                jige += 1;
            } else if (arr[i] > 85) {
                good += 1;
            }
        }
        jige = (jige / students) * 100;
        good = (good / students) * 100;
        System.out.println(jige + "%");
        System.out.println(good + "%");
        scan.close();
    }


    /**
     * 数组的反转
     * 123456 =654321
     */
    public static int[] reversalArr(int[] n) {
        //结尾
        int end = n.length - 1;
        //死循环判断，直到begin和end相遇，就停，循环一次交换一次
        for (int i = 0; i < end; i++) {
            //交换
            int box = n[i];
            n[i] = n[end];
            n[end] = box;
            end--;
        }

        return n;
    }


    /**
     * 算出1-2022中有多少个质数
     * <p>
     * <p>
     * 诶氏  无非就是数组中去去掉质数的倍数，给一个数组打上标记
     */
    @Test
    public void test() {
        int n = 2022;
        boolean[] isPrime = new boolean[n + 1];//避免数组越界
        int count = 0;

        //因为从二开始,一定会去把二的倍数全部都筛选掉,二的倍数都会被标记为合数
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j = i; j <= n; j += i) {
                    isPrime[j] = true;//标记为合数
                }
            }
        }
        System.out.println(count);
    }


    /**
     * 算出1900-20222中有多少个质数
     * <p>
     * <p>
     * 诶氏  无非就是数组中去去掉质数的倍数，给一个数组打上标记
     */
    @Test
    public void test2() {
        int n = 2020;
        boolean[] isPrime = new boolean[n + 1];
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i]) {
                //先将所有的非质数给筛选掉
                for (int j = i + i; j <= n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        //到这里就得到了1 - 20222 的质数个数
        for (int i = 1900; i < isPrime.length; i++) {
            if (!isPrime[i]) {
                count++;
            }
        }
        System.out.println(count);

    }

    /**
     * 求出2 -2022 中所有质数的和
     */

    @Test
    public void test3() {
        int n = 10;
        boolean[] isPrime = new boolean[n + 1];
        int result = 0;

        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                result += i;
                //最开始是二一定是一个质数，开始筛选他的倍数
                for (int j = i; j <= n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        System.out.println(result);

    }

    /**
     * 求出1900 - 2022中所有质数的和
     */
    @Test
    public void test4() {
        int n = 2022;
        boolean[] isPrime = new boolean[n + 1];
        int result = 0;

        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                //最开始是二一定是一个质数，开始筛选他的倍数
                for (int j = i + i; j <= n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
        //到这里所有的质数都被标记了,我们只需要从1900开始相加即可
        for (int j = 1900; j < isPrime.length; j++) {
            if (!isPrime[j]) {
                //是质数
                result += j;
            }
        }
        System.out.println(result);
    }


    @Test
    public void work1() {
        int a = 80;
        char c = (char) a;
        System.out.println(c);

    }

    /**
     * 　　F[1] = 1
     * 　　F[2] = 1
     * 　　F[i] = F[i-1] + F[i-2] (i>2)
     * 　　前几个 Fibonacci 数为 1, 1, 2, 3, 5, 8, 13, 21。
     * 　　请问，前100个 Fibonacci 数中，有多少个数是 3 的倍数？
     */
    @Test
    public void work2() {
        int count = 0;
        BigDecimal a = new BigDecimal(1);
        BigDecimal b = new BigDecimal(1);
        BigDecimal c = new BigDecimal(0);
        for (int i = 2; i <= 100; i++) {
            c = a.add(b);
            a = b;
            b = c;
            if (new BigInteger(c.toString()).mod(new BigInteger("3")).intValue() == 0) {
                count++;
            }
        }
        System.out.println(count);

    }

    /**
     * 　一个身份证号码有 18 位数字或字母组成。其中前17位必须是数字，最后一位可能是数字或字母X。
     * 　　身份证号码满足一定的校验规则。
     * 　　令身份证号从右到左依次标号为 1 到 18，其中标号为 i 的位的位权设置为 2^(i-1) mod 11 （2的i-1次方除以 11 的余数）。
     * 　　将每一位的数值乘以位权后相加，得到的结果除以 11 的余数应当为 1。其中最后一位（标号为1）中如果出现字母 X，看成数字 10。
     * 　　小明的身份证号前 17 位为 11010120210221999，请问小明身份证的最后一位是多少？
     */
    @Test
    public void work3() {
        int count = 0;
        int[] arr = {0, 1, 1, 0, 1, 0, 1, 2, 0, 2, 1, 0, 2, 2, 1, 9, 9, 9};
        reversalArr(arr);
        for (int i = 1; i < arr.length; i++) {
            //先得到权值
            double v = Math.pow(2, i - 1) % 11;
            //得到的结果
            count += v * arr[i];
        }
        //count已经计算完毕，17位的和，我们将这个和 与 2^(18-1) mod 11 的权值 分别去乘以 1-10 然后 +上之前的和
        for (int i = 0; i <= 10; i++) {
            //第十八个数字的权值
            double temp = Math.pow(2, 0) % 11;//7
            if ((count + (temp * i)) % 11 == 1) {
                if (i == 10) System.out.println("X");
                else System.out.println(i);
            }
        }
    }

    /**
     * 给定一个单词，请将这个单词的首字母大写，后面的所有字母小写。
     */
    @Test
    public void work4() {
        String s = "INforMation";
        String end = s.substring(1);
        String first = s.substring(0, 1);
        end = end.toLowerCase();
        first = first.toUpperCase();
        String result = first + end;
        System.out.println(result);
    }


    /**
     * 小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组 成，有些单词很长
     * ，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。
     * 现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这个字母出现的次数。
     */
    @Test
    public void work5() {
        //97-122 a-z
        //65-90 A-Z
        String t = "aaaabbbbbbbbbbbbbbbbbbbbaa";
        int maxNum = 0;
        char maxStr = 0;
        int[] arr = new int[26];
        for (int i = 0; i < t.length(); i++) {
            arr[t.charAt(i) - 'a'] += 1;
        }
        maxNum = arr[0];
        maxStr = 'a';
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
                maxStr = (char) (i + 97);
            }
        }

        System.out.println(maxStr);
        System.out.println(maxNum);
    }

    /**
     * 小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
     * <p>
     * 如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。
     * <p>
     * 请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。
     * <p>
     * 输入的第一行包含一个整数 ，表示考试人数。
     * <p>
     * 接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
     * 输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。
     */
    @Test
    public void test6() {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();//总人数
        int[] mark = new int[total];
        for (int i = 0; i < total; i++) {
            mark[i] = sc.nextInt();
        }
        int jige = 0;
        int youxiu = 0;
        for (int i : mark) {
            //得到每一个学生的成绩
            if (i >= 60 && i < 85) {
                jige++;
            } else if (i >= 85) {
                youxiu++;
            }
        }
        System.out.println(((double) jige / total) * 100 + "%");

    }

    @Test
    public void test7() {
        long result = (long) 1024 * 1024 * 256 * 8 / 32;
        System.out.println(result);
    }

    @Test
    public void test8() {
        Scanner sc = new Scanner(System.in);
        long l = sc.nextLong();
        Date date = new Date(l);
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("HH:mm:ss");
        String s = simpleDateFormat.format(date);
        System.out.println(s);
        sc.close();
    }

    @Test
    public void test9() {

        Calendar c = Calendar.getInstance();
        c.set(2000, 1 - 1, 1);
        //平年的天数
        int run = 0;
        int ping = 0;
        for (int i = 2000; i <= 2020; i++) {
            //算出闰年
            if (i % 4 == 0 || i % 100 == 0) {
                //当前的年是闰年，二月有29天
                run++;
            } else {
                ping++;
            }
            //计算一个7天加一个两千米，每一个月加一个两千米
        }
        //已经得到了闰年和平年的数量之后进行判断然后相加
        //每七天要+1000，每个月也要+1000
        //也就是count = (总天数/7)
        int rundaypao = run * 366;
        int result1 = (rundaypao / 7);//算出要加多少千米 这是闰年的星期的
        int result2 = (rundaypao / 366);//算出要加多少千米 这是平年的月初
        rundaypao += result1 + result2;
        int pingdaypao = ping * 365;
        int result3 = (pingdaypao / 7);
        int result4 = (pingdaypao / 366);
        pingdaypao += result3 + result4;
        System.out.println(rundaypao + pingdaypao);
    }

    /*
    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     */
    public static int[] twoSumHighLevel(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            //用目标值减去当前的值,然后去hashmap中寻找这个值的下标
            int number = target - nums[i];
            Integer numberIndex = hashMap.get(number);
            if (null != numberIndex) {
                //说明能找到，那我们给结果数组赋值并且返回结束当前循环
                result[0] = i;
                result[1] = numberIndex;
                break;
            } else {
                //没找到就将当前的值加入hashmap,key为值,value为值的下标
                hashMap.put(nums[i], i);
            }
        }
        return result;
    }


    /*
    给你两个按 非递减顺序 排列的整数数组nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int index = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //依次比较,把较小的那个放进temp中
                if (nums1[i] > nums2[j]) {
                    temp[index] = nums2[j];
                    index++;
                } else {
                    temp[index] = nums1[i];
                    index++;

                }
            }
        }
        //这里就得到了一个有序的数组了
        nums1 = temp;
    }

    /**
     * 小蓝特别喜欢 22，今年是公元 20202020 年，
     * 他特别高兴。 他很好奇，在公元 11 年到公元 20202020 年（包含）中，有多少个年份的数位中包含数字 22？
     */
    @Test
    void haveTwo() {
        int count = 0;
        for (int i = 1; i <= 2020; i++) {
            String temp = i + "";
            if (temp.contains("2"))count++;
        }
        System.out.println(count);
    }
    /**
     * 字母转换大写
     * -32就可以了
     * 但是java自带的嘛，不用白不用
     */
    @Test
    void toUpCase() {
        Scanner scanner = new Scanner(System.in);
        System.out.println(scanner.nextLine().toUpperCase());
        scanner.close();
    }
    /**
     * 字母转换大写
     * -32就可以了
     * 但是java自带的嘛，不用白不用
     */
    @Test
    void L() {
        System.out.println(76);
    }

}